The Universal Serial Bus (USB) is a half duplex single logical wire which permits relatively high speed serial communication between a host system bus and devices on the USB. The USB supports “USB devices” such as keyboards, joy sticks, pointing devices, mice and audio speakers. In order to execute transactions (i.e. data transfers) on the bus, the host controller must service a schedule, which is a set of data structures in shared memory. These data structures are known as elements, with one element corresponding to each endpoint/device coupled to the bus. One particular subset of elements is organized into a circular linked list, where each list element describes the control and buffer information for the host controller to conduct USB transactions to a particular device on the USB. The host controller services the schedule by repeatedly traversing the circular linked list executing bus transactions as appropriate. This means the host controller will read a list element, execute a transaction, and then write back the results to the element. It should be noted that a transaction will be executed only if the list element control bits indicate that it is appropriate (e.g. a buffer is available).
Additionally, the USB has flow control built into the bus protocol. Thus, the host controller will issue a request for data (e.g. a read), and the device will return either a data packet or a flow control handshake (e.g. flow control event) indicating that it does not currently have data available. Depending on the circumstances, this flow control event is known as a Nak or a Nyet, per Enhanced Host Controller Interface Specification for USB, Revision. 95, Nov. 10, 2000, available on the Internet at the following website: http://developer.intel.com/technology/usb/ehcispec.htm. These flow control events are very short transactions. As described below, this can cause problems.
During operation, devices can issue flow control events much or even most of the time. There are two negative consequences to this behavior. First, the flow control events are very short, and when most, or all, of the devices represented in the schedule are mostly issuing flow control events, the host controller is able to traverse the circular list very quickly, occupying significant system bandwidth in the process. For example, a host controller following the protocol set forth in USB Specification, Version 1.0, Jan. 19, 1996, was measured utilizing 70% of the Peripheral Component Interconnect bus traversing the schedule but not moving any data. Second, the flow control events occupy bus time which could be used by other devices that have data to move.